#include "DynamicArray.h"
#include<iostream>
#include<cmath>

DynamicArray::DynamicArray():capacity(10),size(0),Freeptr(nullptr),Compare(nullptr),CompareBig(nullptr),Print(nullptr),CompareArray(nullptr)
{
    this->a = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &array)
{
    this->size = array.size;
    this->capacity = array.capacity;
    this->a = new ElementType[capacity];
    
    this->Freeptr  = array.Freeptr;
    this->CompareBig = array.CompareBig;
    this->Compare = array.Compare;
    this->CompareArray = array.CompareArray;
    this->Print = array.Print;

    for(int i=0;i < this->size; i++)
    {
        this->a[i] = array.a[i];
    }
}

void DynamicArray::operator=(const DynamicArray &array)
{
    delete []this->a;
    this->size = array.size;
    this->capacity = array.capacity;
    this->a = new ElementType[capacity];
    
    this->Freeptr  = array.Freeptr;
    for(int i=0;i < this->size; i++)
    {
        this->a[i] = array.a[i];
    } 
}

DynamicArray::~DynamicArray()
{
    if (Freeptr) 
    {
        // for(int i=0;i<size;i++)
        // {
            Freeptr(a);
        // }
    }
    
    delete []a;
}




// 尾插法
void DynamicArray::InsertTail(const ElementType &element)
{
    if(size >= capacity)
    {
        capacity *=2;
        ElementType *newptr = new ElementType[capacity];
        for(int i=0;i<size;i++)
        {
            newptr[i] = a[i];
        }
        
        for (int i = 0; i < size; i++)
        {
            if (Freeptr)
            {
                Freeptr(a[i]);
            }
        }
        delete[] a;
        a = newptr;
    }
    a[size++] = element;
}




// 头插法
void DynamicArray::InsertHead(const ElementType&element)
{
    if(size >= capacity)
    {
        capacity *=2;
        ElementType *newptr = new ElementType[capacity];
        for(int i=0; i < size ; i++)
        {
            newptr[i] = a[i];
        }
        for (int i = 0; i < size; i++)
        {
            if (Freeptr)
            {
                Freeptr(a[i]);
            }
        }
        delete[] a;
        a = newptr;
    }
    
    for(int i = size;i > 0;i--)
    {
        a[i] = a[i-1];
    }

    a[0] = element;
    this->size++;
}




// 中间插入
void DynamicArray::InsertByIndex(const ElementType &element, int index)
{

    if(index < 0 && index > size)
    {
        std::cout<<"非法插入位置\n";
    }

    if(size >= capacity)
    {
        capacity *=2;
        ElementType *newptr = new ElementType[capacity];
        for(int i=0; i < size ; i++)
        {
            newptr[i] = a[i];
        }
        
        for (int i = 0; i < size; i++)
        {
            if (Freeptr)
            {
                Freeptr(a[i]);
            }
        }
        delete[] a;
       
        a = newptr;
    }

    for(int i = size;i > index;i--)
    {
        a[i] = a[i-1];
    }
    
    a[index] = element;
    this->size++;

}






// 按值查找
// DynamicArray 
DynamicArray DynamicArray::FindByElement( ElementType element)
{
     DynamicArray result;

    for(int i=0;i<this->size;i++)
    {
        if(Compare(this->a[i] , element))

            result.InsertTail(a[i]);
    }   
   
    return result;

}










// 按位置删除

void DynamicArray::RemovrByIndex(int Index)
{
    if(Index < 0 || Index >= this->size)
    {
        std::cout<<"无法删除这个位置的数!"<<std::endl;
        return;
    }
    for (int i = Index; i < this->size - 1; i++)
    {
        this->a[i] = this->a[i+1];       
    }
    this->size--;   
}




DynamicArray::ElementType DynamicArray::FindByIndex(int index)
{
    if(index < 0 || index >= this->size)
    {
        std::cout<<"无法找到这个位置的数!"<<std::endl;
        return nullptr;
    }
    return this->a[index];
}




void DynamicArray::UpdateByIndex(int index, const ElementType &element)
{
    // if(index < 0 || index >= this->size)
    // {
    //     std::cout<<"无法修改这个位置的数!"<<std::endl;
    //     return;
    // }
    
    // a[index] = element;

    ElementType p = FindByIndex(index);
    if(p)
        {    p= element;
            a[index] = p;
        }
}



void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    for(int i=0;i<size;i++)
    {
        if(Compare(this->a[i],oldValue))
            a[i] = newValue;
    }
}

// 按值删除
void DynamicArray::RemovrByElement(ElementType element)
{
    for(int i=0;i<this->size;i++)
    {
        if(this->Compare(a[i],element))
        {
            RemovrByIndex(i);
            i--;
        }
    }
}




void DynamicArray::Sort()
{
    FastSort( 0 , size-1, 0 , 2 * log2(size));
}




void DynamicArray::Duplicate()  //      O(n)
{
    for(int i=1;i < size;i++)
    {
        if(a[i]==a[i-1])
        {
            RemovrByIndex(i);
            i--;
        }
    }
}




// 归并排序:双指针
DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    int first =0;
    int second = 0;
    DynamicArray result;
    while(first<this->size && second<a.size)
    {
        if(CompareBig(a.a[second],this->a[first]))
                    result.InsertTail(this->a[first++]);
        else
                    result.InsertTail(a.a[second++]);
    }
    while(first < this->size)
                    result.InsertTail(this->a[first++]);
    while(second < a.size)
                    result.InsertTail(a.a[second++]);
    return result;
}


// 两个数列有序
// 找交集
DynamicArray DynamicArray::FindInterSection(const DynamicArray &array)//O(n)
{
    int first =0;
    int second = 0;
    DynamicArray result;
    while(first < size && second < array.size)
    {
        if(this->Compare(a[first],array.a[second]))
        {
            result.InsertTail(a[first++]);
            second++;
        }
        else if(this->CompareBig(array.a[second],a[first]))
        {
            first++;
        }
        else
        {
            second++;
        }
    } 
    return result; 
}


DynamicArray DynamicArray::FindUnionSet(const DynamicArray&array)
{   
    int first =0;
    int second = 0;
    DynamicArray result;
    while(first < size && second < array.size)
    {
        if(a[first] == array.a[second])
        {
            result.InsertTail(a[first++]);
            second++;
        }
        else if(a[first] < array.a[second])
        {
            result.InsertTail(a[first++]);
        }
        else
        {
            result.InsertTail(array.a[second++]);
        }
    } 
    
    while(first < this->size)
                    result.InsertTail(this->a[first++]);
    while(second < array.size)
                    result.InsertTail(array.a[second++]);    
    result.Duplicate();
    return result;

}

DynamicArray DynamicArray::FindDifference(const DynamicArray &array)
{
    int first =0;
    int second = 0;
    DynamicArray result;
    while(first < size && second < array.size)
    {
        if(a[first] == array.a[second])
        {
            first++;
            second++;
        }
        else if(a[first] < array.a[second])
        {
            result.InsertTail(a[first++]);
        }
        else
        {
            result.InsertTail(array.a[second++]);
        }
    }  
     while(first < this->size)
                    result.InsertTail(this->a[first++]);
    while(second < array.size)
                    result.InsertTail(array.a[second++]);   
    result.Duplicate();
    return result;
}

bool DynamicArray::operator==(const DynamicArray &array)
{
    if(size != array.size)
        return false;
    int index = 0;
    
    while(index < size)
    {
        if( Compare(a[index],array.a[index]) != 0)
            return false;
        index++;
    }
    return true;
}






// 默认有序
bool DynamicArray::IsChild(const DynamicArray &array)
{
    int count = 0;
    for(int i=0;i<size;i++)
    {
        if(a[i] == array.a[count])
        {
            count++;
        }
    }
    return count == array.size;
}




// 截取一段子序列
DynamicArray DynamicArray::Subsquence(int index, int len)
{
    DynamicArray sub;
    
    for(int i = index; i < index + len ; i++)
    {
        sub.InsertTail(a[i]);
    }
    return sub;

}


// 滑动窗口   
bool DynamicArray::IsConChild(const DynamicArray &array) //O( n^2 )
{
    for(int i=0 ; i <= this->size-array.size; i++)
    {
        if(CompareArray(Subsquence(i,array.size),array))
            return true;
    }
    return false;
}



void DynamicArray::FastSort(int start, int end, int deepth, int MaxDeepth)
{
    if(start >= end)
    {
        return;
    }
    // 递归的深度超过最大深度

    if(deepth > MaxDeepth)
    {
        // 改用插入排序
        InsertSort(start,end);

    }
    //如果没有超过最大深度
    // 用快速排序
    else
    {
        // 分组
        int pos = Partition(start,end);
        // 递归
        FastSort(start,pos-1,deepth+1,MaxDeepth);
        FastSort(pos+1,end,deepth+1,MaxDeepth);
    }


}



void DynamicArray::InsertSort(int start, int end)
{
    for(int i=start+1;i<=end;i++)
    {
        int j=i;
        ElementType temp = a[j];
        for(;j>start;j--)
        {
            if(CompareBig(a[j-1],temp))
            {
                a[j]= a[j-1];
            }
            else
                break;
        }
        a[j] = temp;
    }
}

int DynamicArray::Partition(int start, int end)
{
    int left = start;
    int right = end;

    ElementType temp = this->a[left];

    while( left < right )
    {
        while(this->CompareBig(this->a[right],temp)  && left < right)
                    right--;
        if(left < right)
        {
            this->a[left] = this->a[right];
            left++;
        }

        while(this->CompareBig(temp,this->a[left]) && left<right)
                    left++;
        if(left < right)
        {
            this->a[right] = this->a[left];
            right--;
        }
        
    }
    this->a[left] = temp; 
    
    return left;
}

// int DynamicArray::BinarySearch(ElementType element)
// {
//     int left = 0;
//     int right = this->size -1;
//     while(left <= right)
//     {
//         // int mid = left + (right - left) / 2;
//         int mid = (left & right) +((left ^ right) >> 1);
        
//         if(this->CompareBig (this->a[mid],element))
//         {
//             right = mid -1;
//         }
//         else if( this->CompareBig(element,this->a[mid]))
//         {
//             left = mid +1;
//         }
//         else
//             return mid;
//     }
//     return -1;
// }



void DynamicArray::show()
{
    for (int i = 0; i < this->size; i++)
    {
        Print(this->a[i]);
        std::cout<<" "<<std::endl;
    }
}

// void DynamicArray::show(void (*print)(ElementType))
// {
//     for (int i = 0; i < size; i++)
//     {
//         Print(this->a[i]);
//         std::cout<<" "<<std::endl;
//     }
// }





